package kara;

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Properties;

public class A47 {

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N =510;
    static int M=5050;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int[] dist=new int[N];
    static int idx = 1;
    static boolean[] st = new boolean[N];
    static int n;
    static int m;
    static PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
        return a[0] - b[0];
    });
static int dijkStar(){
    Arrays.fill(dist, 0x3f3f3f3f);
    dist[1]=0;
    queue.offer(new int[]{0,1});
    while(!queue.isEmpty()){
        //取队头
        int[] poll = queue.poll();
        int distance=poll[0];
        int ver=poll[1];
        if(st[ver])continue;
        st[ver]=true;
        for(int edge=h[ver];edge!=0;edge=ne[edge]){
            int end=e[edge];
            if(dist[end]>distance+w[edge]){
                dist[end]=distance+w[edge];
                //入队列
                queue.offer(new int[]{dist[end],end});
            }
        }
    }
    return dist[n]==0x3f3f3f3f?-1:dist[n];
}
    public static void main(String[] args) throws IOException {
        String[] s = read.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 1; i <= m; i++) {
            String[] s1 = read.readLine().split(" ");
            int a = Integer.parseInt(s1[0]);
            int b = Integer.parseInt(s1[1]);
            int c = Integer.parseInt(s1[2]);
            add(a,b,c);
        }
        int res = dijkStar();
        log.write(Integer.toString(res));
        log.flush();
        read.close();
        log.close();
    }

    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

}
